#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: max_min_depth.py 
@version:
@time: 2024/01/27

广度优先搜索的特性使该算法非常适用于逐层搜索，既然是逐层搜索，那么用一个变量累计深度，就可最终返回最大深度。

我们仍然借助队列结构来完成广度优先搜索，若想用一个变量累计深度，那么每次要访问某一层的所有节点。

在迭代的while循环中，再嵌套一层while循环用于访问某一层的全部节点之后，对深度变量自增，而后继续执行下一层循环。

定义求最大深度的函数名为max_depth
"""

from collections import deque


def max_depth(root):
    if not root:
        return 0
    ans = 0
    queue = deque([root])
    while queue:
        tmp = []
        while queue:
            node = queue.popleft()
            if node.left:
                tmp.append(node.left)
            if node.right:
                tmp.append(node.right)
        queue.extend(tmp)
        ans += 1
    return ans


"""
从上向下访问，只要访问到一个叶节点，证明已经到达了与根节点距离最近的叶节点处，此叶节点的深度即为最小深度。

借助队列，如果当前节点为叶子节点，则返回该节点的深度为最终结果；

如果当前节点不满足上述判断且不为空节点，即存在子节点，则将其子节点依次入队。
"""


def min_depth(root):
    if not root:
        return 0
    queue = deque([(1, root)])
    while queue:
        depth, node = queue.popleft()
        if node and not node.left and not node.right:
            return depth
        if node:
            queue.append((depth + 1, node.left))
            queue.append((depth + 1, node.right))


class TreeNode:
    def __init__(self, root):
        self.val = root
        self.left = None
        self.right = None


node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node1.left = node2
node1.right = node3
node3.left = node4
node3.right = node5

print(max_depth(node1))
print(min_depth(node1))
